#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <sys/time.h>
#include <unistd.h>

int		*putTab(int size, int flag){
  
  int	*tab = malloc(sizeof(int) * size);
  int	i;

  for (i = 0; i< size; i++){
    tab[i] = rand() % 1000;
  }
  if (flag == 1) {
    printf("Tableau initial\n");
    for (i =0; i < size; i++){
      printf("%d ", tab[i]);	
    }
    printf("\n");
  }
  return tab;
}

void	fusion(int *tableau, int debut1, int fin1, int fin2)
{
	int *tableau2;
	int debut2 = fin1+1;
	int compteur1 = debut1;
	int compteur2 = debut2;
	int i;
	
	tableau2 = malloc((fin1-debut1+1)*sizeof(int));
	
	for(i=debut1; i<=fin1; i++)
		tableau2[i-debut1] = tableau[i];
	
	for(i=debut1; i<=fin2; i++)
	{ 
		if(compteur1==debut2)
			break;
		else if(compteur2==(fin2+1))
		{
			tableau[i] = tableau2[compteur1-debut1];
			compteur1++;
		}
		else if(tableau2[compteur1-debut1]<tableau[compteur2])
		{
			tableau[i] = tableau2[compteur1-debut1];
			compteur1++;
		}
		else
		{
			tableau[i] = tableau[compteur2];
			compteur2++;
		}
	}
	
	if (debut1 == 0 && fin2 == 10)
	{
		printf("Tri fusion\n");
		for(i=debut1; i<=fin2; i++)
		{ 
			printf("%d ", tableau[i]);
		}
		printf("\n");
	}
	free(tableau2);
}

void	recurFusion(int *tab, int start, int end)
{
	if (start != end)
	{
		int mid = (start+end)/2;
		recurFusion(tab, start, mid);
		recurFusion(tab, mid+1, end);
		fusion(tab, start, mid, end);
	}
}

void	triFusion(int size, int flag)
{
	int	*tab;
	
	tab = putTab(size, flag);
	recurFusion(tab, 0, size);
}

void	selec(int size, int flag){
	int	min;
	int	save;
	int	index;
	int	*tab;
	int	k, c, j, i;

	tab = putTab(size, flag);
	save = 0;
	index = 0;
	
	for (k = 0; k < size; k++){
		min = tab[k];
		index = k;
		for (c = k; c < size; c++) {
			for (j = k; j < size; j++) {
				if (tab[j] < min){
					min = tab[j];
					index = j;
				}
			}
		}
		save = tab[k];
		tab[k] = min;
		tab[index] = save;
	}
	if (flag == 1){
		printf("Tri selection\n");
		for (i =0; i < size; i++){
			printf("%d ", tab[i]);	
		}
		printf("\n");
	}
}

void	insertion(int size, int flag){
	int		*tab;
	int		min;
	int		c, i;
	
	tab = putTab(size, flag);
	for (i = 1; i < size; i++) {
	  min = tab[i];
	  for (c = i; c > 0 && tab[c - 1] > min; c--) {
	    tab[c] = tab[c - 1];
	  }
	  tab[c] = min;
	}
	if (flag == 1){
	  printf("Tri insertion\n");
	  for (i =0; i < size; i++){
	    printf("%d ", tab[i]);	
	  }
	  printf("\n");
	}
}

void		triBulle(int size, int flag){
	int		*tab;
	int		save;
	int		_swap = 1, j, i;
	
	tab = putTab(10, 1);
	while (_swap) {
		_swap = 0;
		for (j = 0; j < size - 1; j++) {
			if (tab[j] > tab[j + 1]){
				save = tab[j];
				tab[j] = tab[j + 1];
				tab[j + 1] = save;
				_swap = 1;
			}
		}
	}
	if (flag == 1){
		printf("Tri bulle\n");
		for (i =0; i < size; i++){
			printf("%d ", tab[i]);	
		}
		printf("\n");
	}
}



int		main (int argc, const char *argv[]) {
  struct timeval start, end;
  double duration;
  int	i;
	
  if (argc != 2){
    printf("Bad args\n");
    exit (-1);
  }
  if (argv[1][0] == '1'){
    selec(10, 1);
    insertion(10, 1);
    triBulle(10, 1);
    triFusion(10, 1);
  }
	
	
	
	
  else if (argv[1][0] == '2'){
    printf("Tri par selection: ");
    for (i = 0; i < 10; i++){
      gettimeofday(&start, NULL);
      selec(25, 0);
      gettimeofday(&end, NULL);
      duration = (double)(end.tv_usec - start.tv_usec);
      printf( "%1.0f ", duration ); 
    }
    printf("\nTri par insertion: ");
    for (i = 0; i < 10; i++){
      gettimeofday(&start, NULL);
      insertion(25, 0);
      gettimeofday(&end, NULL);
      duration = (double)(end.tv_usec - start.tv_usec);
      printf( "%1.0f ", duration ); 
    }
    printf("\nTri a bulle: ");
    for (i = 0; i < 10; i++){
      gettimeofday(&start, NULL);
      insertion(25, 0);
      gettimeofday(&end, NULL);
      duration = (double)(end.tv_usec - start.tv_usec);
      printf( "%1.0f ", duration ); 
    }
    printf("\nTri a fusion: ");
    for (i = 0; i < 10; i++){
      gettimeofday(&start, NULL);
      triFusion(25, 0);
      gettimeofday(&end, NULL);
      duration = (double)(end.tv_usec - start.tv_usec);
      printf( "%1.0f ", duration ); 
    }
    printf("\n");
  }
  return 0;
}
